package 算法.leetcode.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 *  
 *
 * 示例 1:
 *
 *
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 * 示例 2:
 *
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 *  
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 * https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
 *
 * @author lchenglong
 * @date 2022/3/16
 */
public class Offer07 {
    public class TreeNode {

        int val;

        TreeNode left;

        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static Map<Integer, Integer> dic;

    int[] preOrder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preOrder = preorder;
        dic = new HashMap<Integer, Integer>(preorder.length);
        for (int i = 0; i < inorder.length; i++) {
            dic.put(inorder[i], i);
        }
        TreeNode root = reBuildChildTree(0, 0, preorder.length - 1);
        return root;
    }

    public TreeNode reBuildChildTree(int root, int left, int right) {
        if (left > right) return null;
        TreeNode node = new TreeNode(preOrder[root]);
        // 前根遍历的根节点，划分中根遍历的左右子树
        int i = dic.get(preOrder[root]);
        node.left = reBuildChildTree(root + 1, left, i - 1);
        // 右子树 根节点= 根节点 +（左子树长度）+ 1
        node.right = reBuildChildTree(root + 1 + (i - left ), i + 1, right);
        return node;
    }

    public static void main(String[] args) {
        Offer07 instance = new Offer07();
        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
        TreeNode node = instance.buildTree(preorder, inorder);
        System.out.println(node);
    }



}
